package io.tec.cloud.algorithm.c03_v20220607;

import java.util.ArrayList;
import java.util.List;

public class Code01_ReverseList {
    public static Node revereNodeByList(Node<Integer> head) {
        Node<Integer> curr = head;
        List<Integer> list = new ArrayList<>();
        while (curr != null) {
            list.add(curr.data);
            curr = curr.next;
        }
        Node<Integer> newHead = null;
        Node<Integer> cursor = null;
        int i = 0;
        for (int idx = list.size() - 1; idx >= 0; idx--) {
            final Node<Integer> integerNode = new Node<>(list.get(idx));
            if (i == 0) {
                newHead = integerNode;
                cursor = integerNode;
            } else {
                cursor.next = integerNode;
                cursor = cursor.next;
            }
            i++;
        }
        return newHead;
    }

    public static Node revereNode(Node head) {
        if (head == null) {
            return head;
        }

        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        // 最后一步，head为空，所以要返回新的头节点：pre
        return pre;
    }


    public static Node reverseNode(Node head) {

        if (head == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static DoubleNode revereDoubleNode(DoubleNode head) {
        DoubleNode node = head;
        if (node == null) {
            return node;
        }

        DoubleNode pre = null;
        DoubleNode next;
        while (node != null) {
            next = node.next;
            node.last = next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }


    public static DoubleNode reverseDoubleNode(DoubleNode head) {
        DoubleNode node = head;
        if (node == null) {
            return node;
        }

        DoubleNode pre = null;
        DoubleNode next;
        while (node != null) {
            next = node.next;
            node.last = next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        int testTimes = 1_000_000;
        int maxValue = 500;
        int maxLength = 15;
//        for (int i = 0; i < testTimes; i++) {
//            Node head = generateNode(maxValue, maxLength);
////            Node.print(head);
////            Node.print(Node.copy(head));
//            Node copyHead = Node.copy(head);
////            final Node r1 = revereNode(head);
//            final Node r1 = reverseNode(head);
//            final Node r2 = revereNodeByList(copyHead);
//            Node.print(copyHead);
//            Node.print(r1);
//            Node.print(r2);
//            if (!(r1 == r2 && r1 == null) && !r1.equals(r2)) {
//                System.out.println("error");
//                break;
//            }
//        }

        for (int i = 0; i < testTimes; i++) {
            DoubleNode head = generateDoubleNode(maxValue, maxLength);
//            DoubleNode.print(head);
            DoubleNode copyHead = DoubleNode.copy(head);
//            DoubleNode.print(copyHead);
            final DoubleNode r2 = revereDoubleNode(copyHead);
            final DoubleNode r1 = revereDoubleNode(head);
//            DoubleNode.print(r1);
//            DoubleNode.print(r2);
            if (!(r1 == r2 && r1 == null) && !r1.equals(r2)) {
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }

    private static DoubleNode generateDoubleNode(int maxValue, int maxLength) {
        int length = (int) (Math.random() * maxLength);
        if (length == 0) {
            return null;
        }
        length--;
        DoubleNode head = new DoubleNode((int) (Math.random() * maxValue));
        DoubleNode curr = head;
        DoubleNode pre = null;
        curr.last = pre;
        while (length >= 0) {
            DoubleNode node = new DoubleNode((int) (Math.random() * maxValue));
            curr.next = node;
            node.last = curr;
            pre = curr;
            curr = curr.next;
            length--;
        }
        return head;
    }

    private static Node generateNode(int maxValue, int maxLength) {
        int capacity = 0;
        Node head = null;
        Node curr = null;
        int length = (int) (Math.random() * maxLength);
        while (capacity < length) {
            int num = (int) (Math.random() * maxValue);
            Node node = new Node(num);
            if (capacity == 0) {
                head = node;
                curr = node;
            } else {
                curr.next = node;
                curr = curr.next;
            }
            capacity++;
        }
        return head;
    }
}